package gss.generator;

import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Iterator;
import java.util.Collection;
import java.util.Map;
import java.util.Random;
import java.util.Set;
import java.util.HashSet;
import java.util.Vector;
import java.util.List;
import java.util.ArrayList;

import gss.LineSegment;
import gss.Vertex;
import static gss.BigFractionUtils.*;

import external.RandomIterator;

import org.apache.commons.math.fraction.BigFraction;
import static org.apache.commons.math.fraction.BigFraction.ONE;


/**
 * Utility functions for generators.  Whenever gridsize occurs, it means
 * a length, ie xmax-xmin, or ymax-ymin. The number of lattice points
 * in that grid is gridsize + 1
 */
public class GeneratorUtils {
    private static Random _rdm = new Random();

    public static void setRandom (Random rdm) {
	_rdm = rdm;
    }

    /**
     * Write the given segments and vertices to their respective files.
     * Three files are written for 1) segments (GSS), 2) incidence matrix,
     * and 3) intersection coordinates. Requires segment names for 
     * incidence matrix printing. Does not do intersection computation.
     *
     * @param	linesegs	the collection of generated line segments
     * @param	intersection	the collection of generated vertices with 
     *				visibility
     * @param	gssFile		the path and name to use for the GSS file
     * @param	matrixFile	the path and name to use for the incidence
     *				matrix file
     * @param	verticesFile	the path and name to use for the
     *				intersections file
     */
    public static void writeFiles(
	    Collection<LineSegment> linesegs, 
	    Collection<Vertex> intersections,
	    String gssFile, String matrixFile, String vertexFile
	)
    {
	try{
	    BufferedWriter gssOut =
		new BufferedWriter(new FileWriter(gssFile));
	    BufferedWriter matrixOut =
		new BufferedWriter(new FileWriter(matrixFile)); 
	    BufferedWriter vertexOut =
		new BufferedWriter(new FileWriter(vertexFile));

	    try {
		for(LineSegment templine : linesegs){
		    // write segment to gss file
		    gssOut.write(
			templine.getX1() + " " + templine.getY1() + " "
			+ templine.getX2() + " " + templine.getY2() );
		    gssOut.newLine();
		}

		for(Vertex v : intersections) {
		    // write vertex's matrix row to matrix file
		    matrixOut.write(v.toIncidenceMatrixRow(linesegs));
		    matrixOut.newLine();

		    // write vertex coordinates to intersections file
		    vertexOut.write(v.toString().replace(',', ' '));
		    vertexOut.newLine();
		}
	    } finally {
		if (gssOut != null) { gssOut.close(); }
		if (matrixOut != null) { matrixOut.close(); }
		if (vertexOut !=  null) {vertexOut.close(); }
	    }
	} catch (IOException e){
	    System.err.println("Error: " + e.getMessage());
	    e.printStackTrace();
	} 
    }

    // ***************************
    //   Point Generators PTGEN
    // ***************************

    /**
     * Generates a completely random point within the given grid.
     *
     * @param	gridsize    size of the grid. If xmin==0, xmax is gridsize.
     * @return	a random point
     */
    public static Vertex randomPoint(int gridsize)
    {
	return randomPoint(gridsize, _rdm);
    }

    /**
     * Generates a completely random point within the given grid.
     *
     * @param	gridsize    size of the grid. If xmin==0, xmax is gridsize.
     * @param	rdm	    PRNG object to use
     * @return	a random point
     */
    public static Vertex randomPoint(int gridsize, Random rdm)
    {
	return new Vertex(new BigFraction(rdm.nextInt(gridsize+1)),
		new BigFraction(rdm.nextInt(gridsize+1)));
    }

    /**
     * Generates a completely random point within the given grid.
     *
     * @param	xmin	min x of the window (lower left corner)
     * @param	ymin	min y of the window (lower left corner)
     * @param	xmax	max x of the window (upper right corner)
     * @param	ymax	max y of the window (upper right corner)
     * @param	rdm	    PRNG object to use
     * @return	a random point
     */
    public static Vertex randomPoint(
	    int xmin, int ymin, int xmax, int ymax)
    {
	return randomPoint(xmin, ymin, xmax, ymax, _rdm);
    }

    /**
     * Generates a completely random point within the given grid.
     *
     * @param	xmin	min x of the window (lower left corner)
     * @param	ymin	min y of the window (lower left corner)
     * @param	xmax	max x of the window (upper right corner)
     * @param	ymax	max y of the window (upper right corner)
     * @param	rdm	    PRNG object to use
     * @return	a random point
     */
    public static Vertex randomPoint(
	    int xmin, int ymin, int xmax, int ymax, Random rdm)
    {
	int x = rdm.nextInt(xmax - xmin+1) + xmin;
	int y = rdm.nextInt(ymax - ymin+1) + ymin;
	return new Vertex(x,y);
    }

    /**
     * Selects a random vertex from the given list.
     *
     * @param	vertices    list of intersection points to choose from
     * @return	a random vertex from the specified list
     */
    public static Vertex randomVertex(List<Vertex> vertices) {
	return randomVertex(vertices, _rdm);
    }

    /**
     * Selects a random vertex from the given list.
     *
     * @param	vertices    list of intersection points to choose from
     * @param	rdm	    PRNG object to use
     * @return	a random vertex from the specified list
     */
    public static Vertex randomVertex(List<Vertex> vertices, Random rdm) {
	return vertices.get(rdm.nextInt(vertices.size()));
    }

    // ***************************
    //  Segment Generators SEGGEN
    // ***************************

    /**
     * Generates a completely random line segment within the given grid.
     *
     * @param	gridsize    size of grid to fit segment in
     * @return	LineSegment with completely random endpoint coordinates.
     */
    public static LineSegment randomSegment(int gridsize) {
	return randomSegment(gridsize, _rdm);
    }

    /**
     * Generates a completely random line segment within the given grid.
     *
     * @param	gridsize    size of grid to fit segment in
     * @param	rdm	    PRNG object to use
     * @return	LineSegment with completely random endpoint coordinates.
     */
    public static LineSegment
	randomSegment(int gridsize, Random rdm)
    {
	Vertex a = randomPoint(gridsize, rdm);
	Vertex b = null;
	do {
	    b = randomPoint(gridsize, rdm);
	} while (a.equals(b));
	return new LineSegment(a, b);
    }

    /**
     * Generates a random line segment that is guaranteed to intersect
     * at least one segment in the collection of existing segments 
     * without overlapping any.
     *
     * @param	segments    a collection of existing segments
     * @param	gridsize    size of grid to fit segment in
     * @return	the generated line segment
     */
    public static LineSegment randomIntersectingSegment (
	    List<LineSegment> segments, int gridsize )
    {
	return randomIntersectingSegment(segments, gridsize, _rdm);
    }

    /**
     * Generates a random line segment that is guaranteed to intersect
     * at least one segment in the collection of existing segments 
     * without overlapping any.
     *
     * @param	segments    a collection of existing segments
     * @param	gridsize    size of grid to fit segment in
     * @param	rdm	    PRNG object to use
     * @return	the generated line segment
     */
    public static LineSegment randomIntersectingSegment (
	    List<LineSegment> segments, int gridsize, Random rdm )
    {
	// choose the random segment
	LineSegment segment = segments.get(rdm.nextInt(segments.size()));
	//choose the first point
	Vertex pointA = null;
	do {
	    pointA = randomPoint(gridsize, rdm);
	} while (segment.onLine(pointA));

	//choose the second point	
	Vertex pointB = null;
	pointB = randomIntersectingPoint(
		segment, pointA, 0, 0, gridsize, gridsize, rdm);
	// pointB == null means randomIntersectingPoint failed
	if ( pointB == null ) {
	    // recurse and try again with new pointA
	    return randomIntersectingSegment(
		    segments, gridsize, rdm);
	}
	// else pointB is not null and also cannot be equal to pointA
	// (see comment to randomIntersectingPoint)
	LineSegment seg = new LineSegment(pointA, pointB);

	if ( !noOverlap(seg, segments) ) {
	    return randomIntersectingSegment(
		    segments, gridsize, rdm);
	}

	return seg;
    }

    /**
     * Tries to generate a line segment from one intersection to another
     * without overlapping any existing segments. This is not always 
     * possible so null is returned on failure.
     * REQ: vertices contains at least 2 segments
     * @param	vertices    list of intersection points to choose from
     * @param	segments    collection of existing segments 
     * @return	a LineSegment connecting a vertex to a vertex without 
     *	    overlapping existing segments or null if none was found
     */
    public static LineSegment vertexToVertex(
	    List<Vertex> vertices,
	    Collection<LineSegment> segments)
    {
	return vertexToVertex(vertices, segments, _rdm);
    }

    /**
     * Tries to generate a line segment from one intersection to another
     * without overlapping any existing segments. This is not always 
     * possible so null is returned on failure.
     * REQ: vertices contains at least 2 segments
     * @param	vertices    list of intersection points to choose from
     * @param	segments    collection of existing segments 
     * @param	rdm	    PRNG object to use
     * @return	a LineSegment connecting a vertex to a vertex without 
     *	    overlapping existing segments or null if none was found
     */
    public static LineSegment vertexToVertex(
	    List<Vertex> vertices,
	    Collection<LineSegment> segments,
	    Random rdm)
    {
	Iterator<Vertex> P_itr = new RandomIterator<Vertex>(vertices, rdm);
	Iterator<Vertex> Q_itr = null;
	LineSegment seg = null;

	Vertex P = null;
	Vertex Q = null;
	boolean success = false;
	while (P_itr.hasNext()) {
	    P = P_itr.next();
	    Q_itr = new RandomIterator<Vertex>(vertices, rdm);
	    while (Q_itr.hasNext()) {
		Q = Q_itr.next();
		if (!P.equals(Q)) {
		    seg = new LineSegment(P,Q);
		    if (noOverlap(seg, segments)) {
			return seg;
		    }
		}
	    }
	}
	return null;
    }

    /**
     * Generates a LineSegment with one endpoint on the specified
     * intersection and the other at a random point, making sure the
     * generated segment does not overlap any existing segments.
     *
     * @param	point	    the vertex to use 
     * @param	segments    collection of existing segments
     * @param	xmin	    min x of the window (lower left corner)
     * @param	ymin	    min y of the window (lower left corner)
     * @param	xmax	    max x of the window (upper right corner)
     * @param	ymax	    max y of the window (upper right corner)
     * @return	a LineSegment with one endpoint on an intersection point 
     *		that does not overlap any existing segments. The
     *		intersection point is guaranteed to be Vertex1 of the 
     *		returned segment.
     */
    public static LineSegment vertexToRandom(
	    Vertex point,
	    Collection<LineSegment> segments,
	    int xmin, int ymin, int xmax, int ymax)
    {
	return vertexToRandom(point, segments,
		xmin, ymin, xmax, ymax, _rdm);
    }

    /**
     * Generates a LineSegment with one endpoint on the specified
     * intersection and the other at a random point, making sure the
     * generated segment does not overlap any existing segments.
     *
     * @param	point	    the vertex to use 
     * @param	segments    collection of existing segments
     * @param	xmin	    min x of the window (lower left corner)
     * @param	ymin	    min y of the window (lower left corner)
     * @param	xmax	    max x of the window (upper right corner)
     * @param	ymax	    max y of the window (upper right corner)
     * @param	rdm	    PRNG object to use
     * @return	a LineSegment with one endpoint on an intersection point 
     *		that does not overlap any existing segments. The
     *		intersection point is guaranteed to be Vertex1 of the 
     *		returned segment.
     */
    public static LineSegment vertexToRandom(
	    Vertex point,
	    Collection<LineSegment> segments,
	    int xmin, int ymin, int xmax, int ymax,
	    Random rdm)
    {
	Vertex pointB = null;
	do {
	    pointB = randomPoint(xmin, ymin, xmax, ymax, rdm);
	} while (point.equals(pointB) || 
		!noOverlap(new LineSegment(point, pointB), segments));

	return new LineSegment(
	    point.getX(), point.getY(), pointB.getX(), pointB.getY());
    }

    /**
     * Generates a LineSegment with one endpoint on a randomly chosen
     * intersection and the other at a random point, making sure the
     * generated segment does not overlap any existing segments.
     *
     * @param	vertices    list of intersection points to choose from
     * @param	segments    collection of existing segments
     * @param	gridsize    size of grid to fit segment in
     * @return	a LineSegment with one endpoint on an intersection point 
     *		that does not overlap any existing segments. The 
     *		intersection point is Vertex1 and the random point is 
     *		Vertex2.
     */
    public static LineSegment randomVertexToRandom(
	    List<Vertex> vertices,
	    Collection<LineSegment> segments,
	    int gridsize)
    {
	return randomVertexToRandom(vertices, segments, gridsize, _rdm);
    }

    /**
     * Generates a LineSegment with one endpoint on a randomly chosen
     * intersection and the other at a random point, making sure the
     * generated segment does not overlap any existing segments.
     *
     * @param	vertices    list of intersection points to choose from
     * @param	segments    collection of existing segments
     * @param	gridsize    size of grid to fit segment in
     * @param	rdm	    PRNG object to use
     * @return	a LineSegment with one endpoint on an intersection point 
     *		that does not overlap any existing segments. The 
     *		intersection point is Vertex1 and the random point is 
     *		Vertex2.
     */
    public static LineSegment randomVertexToRandom(
	    List<Vertex> vertices,
	    Collection<LineSegment> segments,
	    int gridsize, Random rdm)
    {
	Vertex pointA = randomVertex(vertices, rdm);
	Vertex pointB = null;
	do {
	    pointB = randomPoint(gridsize, rdm);
	} while (pointA.equals(pointB) || 
		!noOverlap(new LineSegment(pointA, pointB), segments));
    
	return new LineSegment(
	    pointA.getX(), pointA.getY(), pointB.getX(), pointB.getY());
    }

    // ******************************
    // Specialized Generators SPECGEN
    // ******************************

    /**
     * Generates a star structure using the specified center vertex and 
     * random endpoints within the specified window.
     *
     * @param	num	    number of rays to generate. This is not 
     *			    necessarily the degree because there is 
     *			    no guarantee that it won't generate two 
     *			    opposing (collinear) rays. It makes very little
     *			    sense to call this method with num less than 2
     * @param	center	    the center vertex of the star
     * @param	xmin	    min x of the window (lower left corner)
     * @param	ymin	    min y of the window (lower left corner)
     * @param	xmax	    max x of the window (upper right corner)
     * @param	ymax	    max y of the window (upper right corner)
     * @return	a set of LineSegment's representing the star. Further,
     *		the segments are guaranteed to have the center as 
     *		their Vertex1
     */
    public static Set<LineSegment> randomRayStar(int num, Vertex center,
	    int xmin, int ymin, int xmax, int ymax)

    {
	return randomRayStar(num, center, xmin, ymin, xmax, ymax, _rdm);
    }

    /**
     * Generates a star structure using the specified center vertex and 
     * random endpoints within the specified window.
     *
     * @param	num	    number of rays to generate. This is not 
     *			    necessarily the degree because there is 
     *			    no guarantee that it won't generate two 
     *			    opposing (collinear) rays. It makes very little
     *			    sense to call this method with num less than 2
     * @param	center	    the center vertex of the star
     * @param	xmin	    min x of the window (lower left corner)
     * @param	ymin	    min y of the window (lower left corner)
     * @param	xmax	    max x of the window (upper right corner)
     * @param	ymax	    max y of the window (upper right corner)
     * @param	rdm	    PRNG object to use
     * @return	a set of LineSegment's representing the star. Further,
     *		the segments are guaranteed to have the center as 
     *		their Vertex1
     */
    public static Set<LineSegment> randomRayStar(int num, Vertex center,
	    int xmin, int ymin, int xmax, int ymax,
	    Random rdm) 
    {
	Set<LineSegment> starSegs = new HashSet<LineSegment>();
	for (int i=0; i<num; i++) {
	    starSegs.add(vertexToRandom(center, starSegs,
		    xmin, ymin, xmax, ymax, rdm) );
	}
	return starSegs;
    }
    // ***************************
    //   Utility Functions UTIL
    // ***************************

    /**
     * Probably attempts to extends given segment, with the constraints of
     * staying within gridsize and noOverlap, using probExtend as the 
     * probability.
     *
     * @param	probExtend  probability to extend the vertex endpoint
     * @param	extendDir   direction to extend: 1 for first vertex, 2 for
     *			    second vertex, 3 for both
     * @param	seg	    segment to extend
     * @param	segments    collection of segments to test overlap against
     * @param	gridsize    size of grid to fit segment in
     * @return	the extended segment, or the original if extending failed
     */
    public static LineSegment probExtendSegment (
	    double probExtend,
	    int extendDir,
	    LineSegment seg,
	    Collection<LineSegment> segments,
	    int gridsize)
    {
	return probExtendSegment(
		probExtend, extendDir, seg, segments, gridsize, _rdm);
    }

    /**
     * Probably attempts to extends given segment, with the constraints of
     * staying within gridsize and noOverlap, using probExtend as the 
     * probability.
     *
     * @param	probExtend  probability to extend the vertex endpoint
     * @param	extendDir   direction to extend: 1 for first vertex, 2 for
     *			    second vertex, 3 for both
     * @param	seg	    segment to extend
     * @param	segments    collection of segments to test overlap against
     * @param	gridsize    size of grid to fit segment in
     * @param	rdm	    PRNG object to use
     * @return	the extended segment, or the original if extending failed
     */
    public static LineSegment probExtendSegment (
	    double probExtend,
	    int extendDir,
	    LineSegment seg,
	    Collection<LineSegment> segments,
	    int gridsize, Random rdm)
    {
	// each endpoint is handled independently and has probExtend
	// probability of being extended
	boolean ext1 = (extendDir == 1 || extendDir == 3) &&
	    (probExtend >= rdm.nextDouble());
	boolean ext2 = (extendDir == 2 || extendDir == 3) && 
	    (probExtend >= rdm.nextDouble());
	LineSegment seg1 = null;
	LineSegment seg2 = null;
	if (ext1) {
	    seg1 = seg.extend(1, 0, 0, gridsize, gridsize);
	    if (noOverlap(seg1, segments)) {
		seg = seg1;
	    }
	}
	if (ext2) {
	    seg2 = seg.extend(2, 0, 0, gridsize, gridsize);
	    if (noOverlap(seg2, segments)) {
		seg = seg2;
	    }
	}

	return seg;				   
    }

    /**
     * Calculates relevant intersections of the rays PA, PB, and segment PB
     * along the vertical sweep-line. Critical points (intersections)
     * delimit regions of points marked out by the 3 segments/rays
     * mentioned. One region will contain points Q such that PQ intersects
     * l.  See algorithm.txt for the full description.
     *
     * @param	Xsweep	    the x coordinate of the vertical sweep-line
     * @param	P	    an external point, NOT collinear to l
     * @param	l	    a line segment 
     * @return	a collection of no more than 2 critical points
     */
    private static Collection<BigFraction>
	findCriticalPoints (BigFraction Xsweep, Vertex P, LineSegment l)
    {
	Vertex A = l.getVertex1();
	Vertex B = l.getVertex2();
	BigFraction PX = P.getX();
	BigFraction AX = A.getX();
	BigFraction BX = B.getX();
	LineSegment PA = new LineSegment(P, A);
	LineSegment PB = new LineSegment(P, B);
	Collection<BigFraction> criticalPoints
	    = new HashSet<BigFraction>(2); // maximum 2 crit points

	//	PA critical point
	int px_comp_ax = PX.compareTo(AX);
	int ax_comp_x  = AX.compareTo(Xsweep);
	// if AX between PX and x, inclusive of x, exclusive of PX
	if ( px_comp_ax < 0 && ax_comp_x <= 0
		|| ax_comp_x >= 0 && px_comp_ax > 0 )
	{
	    criticalPoints.add(PA.yValue(Xsweep));
	}

	//	PB critical point
	int px_comp_bx = PX.compareTo(BX);
	int bx_comp_x  = BX.compareTo(Xsweep);
	// if BX between PX and x, inclusive of x, exclusive of PX
	if ( px_comp_bx < 0 && bx_comp_x <= 0
		|| bx_comp_x >= 0 && px_comp_bx > 0 )
	{
	    criticalPoints.add(PB.yValue(Xsweep));
	}

	// segment l critical point
	if (l.isNotVertical() && 
		( ax_comp_x <= 0 && bx_comp_x >= 0
		  || bx_comp_x <= 0 && ax_comp_x >= 0 ) )
	{
	    criticalPoints.add(l.yValue(Xsweep));
	}

	/* TODO DELETEME
	System.out.print(Xsweep + ":  ");
	for (BigFraction f : criticalPoints) {
	    System.out.print(f + "  ");
	}
	System.out.println();
	*/

	return criticalPoints;
    }

    /**
     * Picks a random point q such that pq intersects l. 
     *
     * @param	l	a line segment in the window
     * @param	P	a point in the window not collinear to l
     * @param	xmin	min x of the window (lower left corner)
     * @param	ymin	min y of the window (lower left corner)
     * @param	xmax	max x of the window (upper right corner)
     * @param	ymax	max y of the window (upper right corner)
     * @return	A randomly chosen point Q such that PQ intersects l or null
     *		if none can be found.
     *		Obviously Q cannot be equal to P, since P is not collinear
     *		to l and PQ intersects l.
     */
    public static Vertex randomIntersectingPoint(LineSegment l, Vertex P, 
	    int xmin, int ymin, int xmax, int ymax)
    {
	return randomIntersectingPoint(l, P, xmin, ymin, xmax, ymax, _rdm);
    }

    /**
     * Picks a random point q such that pq intersects l. 
     *
     * @param	l	a line segment in the window
     * @param	P	a point in the window not collinear to l
     * @param	xmin	min x of the window (lower left corner)
     * @param	ymin	min y of the window (lower left corner)
     * @param	xmax	max x of the window (upper right corner)
     * @param	ymax	max y of the window (upper right corner)
     * @param	rdm	PRNG object to use
     * @return	A randomly chosen point Q such that PQ intersects l or null
     *		if none can be found.
     *		Obviously Q cannot be equal to P, since P is not collinear
     *		to l and PQ intersects l.
     */
    public static Vertex randomIntersectingPoint(LineSegment l, Vertex P, 
	    int xmin, int ymin, int xmax, int ymax, Random rdm)
    {
	Collection<BigFraction> criticalPoints;
	int pointWidth = xmax-xmin+1;
	int [] y_lArray = new int[pointWidth];
	int [] cumNumLatticeArray = new int[pointWidth];
	for (int x=xmin; x <= xmax; x++) {
	    BigFraction X = new BigFraction(x);

	    // Part 1: finding critical points
	    criticalPoints = findCriticalPoints(X, P, l);

	    // ***********************************
	    // Part 2: counting lattice points
	    // ***********************************
	    // REQ:  gridsize must be within the range of int
	    // PRE : Collection<BigFraction> of size at most 2
	    //	     X, P, l
	    // POST: int y_l = lowest lattice point,
	    //	     int numLattice = number of lattice points
	    //	     perhaps an Interval class should be created for this

	    BigFraction [] critPArray
		= criticalPoints.toArray(new BigFraction[0]);
	    int y_l = 0;
	    int numLattice = 0;
	    if (critPArray.length == 2) {
		BigFraction yhigh = null;
		BigFraction ylow = null;
		if ( critPArray[0].compareTo(critPArray[1]) > 0 ) {
		    yhigh = critPArray[0];
		    ylow = critPArray[1];
		} else {
		    ylow = critPArray[0];
		    yhigh = critPArray[1];
		}
		int y_h = floor(yhigh).intValue();
		y_l = ceiling(ylow).intValue();
		if (y_l > ymax || y_h < ymin) {
		    numLattice = 0;
		} else {
		    if ( y_h > ymax ) y_h = ymax;
		    if ( y_l < ymin ) y_l = ymin;
		    numLattice = y_h - y_l + 1;
		}
	    } else if (critPArray.length == 1) {
		// "random" test point: add one to critical pt
		BigFraction yTest_Upper = critPArray[0].add(ONE);
		// "random" test point: subtract one from critical pt
		BigFraction yTest_Lower = critPArray[0].subtract(ONE);
		// Make sure points not equal
		if ( X.equals(P.getX()) ) {
		    if ( yTest_Upper.equals(P.getY()) ) {
			yTest_Upper = yTest_Upper.add(ONE);
		    } else 
		    if ( yTest_Lower.equals(P.getY()) ) {
			yTest_Lower = yTest_Lower.subtract(ONE);
		    }
		}
		// create the test segments
		LineSegment PQ_Upper = new LineSegment(
			X, yTest_Upper, P.getX(), P.getY());
		LineSegment PQ_Lower = new LineSegment(
			X, yTest_Lower, P.getX(), P.getY());
		// test upper interval
		if (PQ_Upper.intersects(l)) {
		    y_l = ceiling(critPArray[0]).intValue();
		    if (y_l > ymax) {
			numLattice = 0;
		    } else {
			if (y_l < ymin) { y_l = ymin; }
			numLattice = ymax - y_l + 1;
		    }
		} else if (PQ_Lower.intersects(l)) {
		// test lower interval
		    int y_h = floor(critPArray[0]).intValue();
		    if (y_h < ymin) {
			numLattice = 0;
		    } else {
			if (y_h > ymax) { y_h = ymax; }
			y_l = ymin;
			numLattice = y_h - y_l + 1;
		    }
		} else {
		// both intervals failed
		    if (isInteger(critPArray[0])) {
			y_l = critPArray[0].intValue();
			numLattice = 1;
		    } else {
			numLattice = 0;
		    }
		}
	    } else if (critPArray.length == 0) {
		numLattice = 0;
		// no need to set y_l when numLattice == 0
	    }
	    // END counting lattice point

	    // ***********************************
	    // Part 3: Storing sweep-line weights 
	    // ***********************************
	    // PRE : numLattice, y_l
	    //	     2 arrays to store them in
	    //	     x
	    // POST: numLattice and y_l stored in array
	    int xindex = x - xmin;
	    y_lArray[xindex]	       = y_l;
	    cumNumLatticeArray[xindex] = numLattice + 
		(xindex==0 ? 0 : cumNumLatticeArray[xindex-1]);
	}
	/* TODO DELETEME
	for(int i=0; i<pointWidth; i++) {
	    System.out.println(i+": "
		    + y_lArray[i] + "  |  " + cumNumLatticeArray[i]);
	}
	*/

	// ******************************
	// Part 4: choosing random point 
	// ******************************
	int totalLattice = cumNumLatticeArray[pointWidth-1];
	if ( totalLattice == 0 ) { return null; }
	int selected = rdm.nextInt(totalLattice);
	int x = 0;
	while ( x<pointWidth && selected >= cumNumLatticeArray[x] ) { x++; }
	// POST: 0 <= x < pointWidth,
	// x==0 ? 0 : cumNumLatticeArray[x-1]
	//	<= selected < cumNumLatticeArray[x]
	int yoffset = selected - (x==0 ? 0 : cumNumLatticeArray[x-1]);
	int y = y_lArray[x]+yoffset;
	x += xmin;

	return new Vertex(x,y);
    }

    /**
     * Given a line segment l and a point P not on l, find the set of points
     * Q in the grid such that PQ intersects l. Uses brute force, i.e.
     * it checks every single point in the grid.
     *
     * @param	point	    a point not collinear to the segment
     * @param	segment	    a line segment to intersect
     * @param	gridsize    the size of the grid
     * @return	a collection of points Q such that point-Q
     *		intersects segment
     */
    public static Collection<Vertex>
	intersectingPoints(Vertex point, LineSegment segment, int gridsize)
    {
	ArrayList<Vertex> validpts = new ArrayList<Vertex>();
	for(int x = 0; x <= gridsize; x++){
	    for(int y = 0; y <= gridsize; y++){
		BigFraction xcoord = new BigFraction(x);
		BigFraction ycoord = new BigFraction(y);
		// no zero-length segment
		if (xcoord.equals(point.getX()) && 
			ycoord.equals(point.getY()) ) 
		{
		    continue;
		} // else
		LineSegment testline =
		    new LineSegment(xcoord, ycoord,
				    point.getX(), point.getY() );
		if(segment.intersects(testline)) {
		    validpts.add(new Vertex(xcoord, ycoord));
		}
	    }
	}
	return validpts;
    }

    /**
     * Tests if the line segment would overlap an existing one in the 
     * collection.
     *
     * @param	l	    line segment to test
     * @param	segments    collection of existing segments 
     * @return	true if no overlap, false if overlap
     */
    public static boolean noOverlap (
	    LineSegment l, Collection<LineSegment> segments)
    {
	for(LineSegment m : segments){
	    if (l.collinearOverlaps(m)) { return false; }
	}
	return true;
    }

    // ******************************
    //      add methods  ADDING
    // ******************************

    /**
     * Adds vertex to map of vertices, and merges visibility if
     * a vertex with the same coordinates already exists. 
     * Modifies vertices.
     *
     * @param	point	    vertex to add
     * @param	vertices    set of intersection vertices to update
     * @return	true if the Map did not already contain the vertex
     */
    public static boolean addVertex(Vertex point,
	    Map<Vertex, HashSet<LineSegment> > vertices )
    {
	if(vertices.containsKey(point)){
	    vertices.get(point).addAll(point.getVisibility());
	    return false;
	} else{
	    vertices.put(point,
		    new HashSet<LineSegment>(point.getVisibility()));
	    return true;
	}
    }

    /**
     * Adds vertex to map of vertices, and merges visibility if
     * a vertex with the same coordinates already exists. If vertex
     * is new, add it to the list as well. 
     * PRE-REQ:	the map and the list contain the same vertices
     * POST   : the map and the list contain the same vertices
     * Modifies vertices.
     *
     * @param	point	    vertex to add
     * @param	vertices    set of intersection vertices to update
     * @param	vertexList  the same intersection vertices in a list
     */
    public static void addVertex(Vertex point,
	    Map<Vertex, HashSet<LineSegment> > vertices,
	    List<Vertex> vertexlist )
    {
	if( addVertex(point, vertices) ){
	    vertexlist.add(point);
	}
    }

    /**
     * Adds vertex to the list of vertices and merges visibility if
     * a vertex with the same coordinates already exists.
     *
     * @param	point	    vertex to add
     * @param	vertices    list of intersection vertices to update
     */
    public static void addVertex(Vertex point, List<Vertex> vertices){
	int index = vertices.indexOf(point);
	if(index!=-1){
	    vertices.get(index).mergeVisibility(point.getVisibility());
	}
	else{
	    vertices.add(point);
	}
    }    

    /**
     * Adds line segment to the collection and computes
     * intersection vertices, adding them to the vertex set as well.
     * REQ: noOverlap() returns true for all segments.
     * Modifies all collections
     *
     * @param	seg	    line segment to add
     * @param	segments    set of segments to add to
     * @param	vertices    set of intersection vertices to update
     */
    public static void
	addSegmentAndIntersections(LineSegment seg,
	    Collection<LineSegment> segments,
	    Map<Vertex, HashSet<LineSegment> > vertices)
    {
	for (LineSegment l : segments) {
	    if (!seg.isParallelTo(l) && seg.intersects(l)) {
		addVertex(seg.intersectionPoint(l), vertices);
	    }
	}
	segments.add(seg);
    }

    /**
     * Adds line segment to the collection and computes
     * intersection vertices, adding them to both vertices collections.
     * REQ: noOverlap() returns true for all segments.
     * Modifies all collections
     *
     * @param	seg	    line segment to add
     * @param	segments    set of segments to add to
     * @param	vertices    set of intersection vertices to update
     * @param	vertexList  the same intersection vertices in a list
     */
    public static void
	addSegmentAndIntersections(LineSegment seg,
	    Collection<LineSegment> segments,
	    Map<Vertex, HashSet<LineSegment> > vertices,
	    List<Vertex> vertexList)
    {
	for (LineSegment l : segments) {
	    if (!seg.isParallelTo(l) && seg.intersects(l)) {
		addVertex(seg.intersectionPoint(l), vertices, vertexList);
	    }
	}
	segments.add(seg);
    }

    /**
     * Adds a line segment to the collection of line segments, computes
     * intersections and adds them to the intersections collection,
     * and adds the endpoints to the collection of vertices
     *
     * @param	seg		line segment to add
     * @param	segments	set of segments to add to
     * @param	endpoints	set of endpoints to add endpoints to
     * @param	intersections	set of intersection points
     */
    public static void addSegmentEndpointsAndIntersections(
	    LineSegment seg,
	    Collection<LineSegment> segments,
	    List<Vertex> endpoints,
	    List<Vertex> intersections
	)
    {
	addVertex(seg.getVertex1(), endpoints);
	addVertex(seg.getVertex2(), endpoints);
	for (LineSegment l : segments) {
	    if (!seg.isParallelTo(l) && seg.intersects(l)) {
		addVertex(seg.intersectionPoint(l), intersections);
	    }
	}
	segments.add(seg);
    }

    /**
     * Adds a line segment to the collection of line segments, or merges
     * it into an existing segment that overlaps it. The collection passed
     * must allow the removal of objects via Iterator.remove(), and also
     * addAll. 
     *
     * @param	seg	    line segment to add
     * @param	segments    set of segments to add to
     */
    public static void addMergeSegment(
	    LineSegment seg, Set<LineSegment> segments)
    {
	Set<LineSegment> tempSegSet = new HashSet<LineSegment>();
	Iterator<LineSegment> itr = segments.iterator();
	while (itr.hasNext()) {
	    LineSegment l = itr.next();
	    if (seg.collinearOverlaps(l)) {
		seg = seg.mergeOverlapping(l);
		tempSegSet.add(seg);
		itr.remove();
	    }
	}
	segments.addAll(tempSegSet);
    }
}
